package lsg

import (
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
	"gitee.com/ljfirst/algo-go-sdk/tools"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/7/10 02:11
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 打家劫舍
 * 在一条直线上，有n个房屋，每个房屋中有数量不等的财宝，有一个盗 贼希望从房屋中盗取财宝，由于房屋中有报警器，
 * 如果同时从相邻的两个房屋中盗取财宝就会触发报警器。问在不触发报警器的前提下，最多可获取多少财宝？
 * 例如 [5，2，6，3，1，7]，则选择5，6，7
 **/

type LSG_Dynamic struct {
	Sum int
	//Path []int
}

func (m *LSG_Dynamic) Method(array []int) {
	if len(array) == 0 {
		return
	}
	if len(array) == 1 {
		m.Sum = array[0]
		//m.Path = array
		return
	}
	if len(array) == 2 {
		if array[0] > array[1] {
			m.Sum = array[0]
			//m.Path = []int{0}
		} else {
			m.Sum = array[1]
			//m.Path = []int{1}
		}
		return
	}

	m.Sum = 0
	//m.Path = make([]int, 0)
	record := make([]int, len(array), len(array))
	record[0] = array[0]
	record[1] = tools.Max(array[0], array[1])

	for i := 2; i < len(array); i++ {
		record[i] = tools.Max(record[i-1], record[i-2]+array[i], array[i])
		m.Sum = tools.Max(record[i], m.Sum)
	}
}

func (m *LSG_Dynamic) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.LSG, C.Dynamic},
		Desc: &C.Desc{
			Name:       "LSG_Dynamic",
			NameCn:     "最大间隔和:动态规划",
			ParamsDesc: map[string]string{},
			Example:    map[int]string{},
		},
	}
}
